/*
leetcode 128. 最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。


示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
 

提示：

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

*/
#include <unordered_set>
#include <vector>
#include <iostream>
using namespace std;

int longestConsecutive(vector<int>& nums) {

    unordered_set<int> numSet(nums.begin(), nums.end()); // 使用哈希表存储所有数字
    int longestStreak = 0; // 记录最长序列长度

   //遍历哈希表中所有数字
    for (int num : numSet) {

        // 如果当前数字没有前驱（num - 1 不在 numSet 中），它可能是一个序列的起点
        //numSet.find(num - 1) 用来查找 num-1 是否在哈希表里，若在，返回 num-1 的迭代器，跳过 if 
        //若不在，则返回numSet.end()，进入 if 条件里
        if (numSet.find(num - 1) == numSet.end()) {

            int currentNum = num; // 当前数字
            int currentStreak = 1; // 当前序列长度

            // 找到所有连续数字，如果 currentNum + 1 存在于 numSet，说明序列可以继续扩展，否则跳出循环
            while (numSet.find(currentNum + 1) != numSet.end()) {
                currentNum += 1; // 移动到下一个数字，继续判断下一个数字是否在本序列中年可扩展
                currentStreak += 1; // 增加当前序列长度
            }

            // 更新最长序列长度
            longestStreak = max(longestStreak, currentStreak);
        }
    }

    return longestStreak;
}

// 测试
int main() {
    vector<int> nums = {100, 4, 200, 1, 3, 2};
    vector<int> nums2 = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};//[0,3,7,2,5,8,4,6,0,1]
    cout << "longestStreak: " << longestConsecutive(nums2) << endl;
    return 0;
}

/*
以输入数组 {100, 4, 200, 1, 3, 2} 为例：

哈希表初始化：将数组元素存入哈希表：
numSet = {100, 4, 200, 1, 3, 2}

遍历 numSet 中的每个元素：

数字 100：100 - 1 = 99 不在 numSet 中，它是一个序列的起点。
连续数字只有 100，当前序列长度为 1。

数字 4：4 - 1 = 3 在 numSet 中，它不是序列的起点，跳过。

数字 200：200 - 1 = 199 不在 numSet 中，它是一个序列的起点。
连续数字只有 200，当前序列长度为 1。

数字 1：1 - 1 = 0 不在 numSet 中，它是一个序列的起点。
连续数字为 1, 2, 3, 4，当前序列长度为 4。

数字 3 和 2：不是序列的起点，跳过。
结果更新：最长连续序列长度为 4。
*/